package com.zjj.lbw.algorithm.backTrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhanglei.zjj
 * @description leetcode_22. 括号生成，回溯算法解决
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *  
 *
 * 提示：
 *
 * 1 <= n <= 8
 * @date 2023/6/10 17:01
 */
public class GenerateParenthesis_leetcode_22 {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList();
        if (n < 1) {
            return result;
        }
        backtrack(result, n, new StringBuffer(), 0, 0);
        return result;
    }

    public void backtrack(List<String> result, int max, StringBuffer stringBuffer, int leftNum, int rightNum) {
        if (stringBuffer.length() == 2 * max) {
            result.add(stringBuffer.toString());
            return;
        }
        // 当前已使用左括号小于最大值
        if (leftNum < max) {
            stringBuffer.append("(");
            backtrack(result, max, stringBuffer, leftNum + 1, rightNum);

            // 向上回溯
            stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        }
        // 当前已使用右括号小于最大值
        if (rightNum < leftNum) {
            stringBuffer.append(")");
            backtrack(result, max, stringBuffer, leftNum, rightNum + 1);

            // 向上回溯
            stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        }
    }

    public static void main(String[] args) {
        GenerateParenthesis_leetcode_22 entryObj = new GenerateParenthesis_leetcode_22();
        System.out.println(entryObj.generateParenthesis(3));
    }
}
